package cn.ljj;

import cn.lj2.MAXZ14;

import javax.swing.tree.TreeNode;

public class Tchashu110 {
    public static void main(String[] args) {
        Tchashu110.Solution solution = new Tchashu110().new Solution();
    }

//    给定一个二叉树，判断它是否是高度平衡的二叉树。
//mei一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
//      Definition for a binary tree node.

    class Solution {
        public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }

        /**
         * 从上而下
         * @param root
         * @return
         */
/*        public boolean isBalanced(TreeNode root) {
            if (root==null){
                return true;
            }else {
                return Math.abs(height(root.left)-height(root.right))<=1&&isBalanced(root.left)&&isBalanced(root.right);
            }
        }

        public int height(TreeNode root){
            if (root==null){
                return 0;
            }else {
                return Math.max(height(root.left),height(root.right))+1;
            }
        }*/

        public boolean isBalanced(TreeNode root) {
            return height(root) >= 0;
        }
        public int height(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftHeight = height(root.left);
            int rightHeight = height(root.right);
            if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
                return -1;
            } else {
                return Math.max(leftHeight, rightHeight) + 1;
            }
        }
    }

}
